当key值加到sorter后，sorter就会被写到磁盘上的一系列排好序的PMA中，每个PMA的大小大约和暂时数据库的Cache的大小差不多。为了能使调用者按照排好的顺序从sorter中提取key值，所有磁盘上的PMA需要合并到一起。下面这段说明描述了做这件事（归并排序）所需要的数据结构及算法。所描述的数据结构支持通过一趟算法就把任意数量的数组合并起来，并且没有冗余的比较。 数组aIter[]包含了为需要合并的所有PMA准备的迭代器（应该是有多少需要合并的ＰＭＡ，就有多少迭代器，数组aIter[]中的元素就是一个个的迭代器）。一个aIter[]中的迭代器，要么指向一个有效的key值，要么就位于EOF。为方便下面的举例说明，我们假设数组aIter[]有N个元素，N是2的幂，N>=需要被合并的迭代器。多余的aIter[]元素被认为是空的，假设它们位于EOF。数组aTree[]也是有Ｎ个元素，Ｎ的值存储在变量VdbeSorter。nTree中。数组aTree[]的最后(N/2)个元素包含对迭代器Ｋｅｙ值的比较结果。数组aTree[]的第ｉ个元素保存的是aIter[2i-N]和 aIter[2i-N+1]大小比较结果（这句话说明了数组aTree[]和数组aIter[]中元素的对应关系），aIter[2i-N]和 aIter[2i-N+1]二者中，谁更小，就把谁的下标存在数组aTree[]的第ｉ个元素里。因为上面的比较方法，我们认为ＥＯＦ大于任何ＫＥＹ值。如果两个相比较的ｋｅｙ值一样大，则存二者中任意一个所对应的迭代器的下标。数组aTree[]中有(N/4)个元素存的是每四个迭代器所组成的一组中ｋｅｙ值最小的那个迭代器的下标。所以aTree[1]中存有指向最小的ｋｅｙ值的迭代器的下标。aTree[0]没有被使用。 举例： aIter[0] -> Banana aIter[1] -> Feijoa aIter[2] -> Elderberry aIter[3] -> Currant aIter[4] -> Grapefruit aIter[5] -> Apple aIter[6] -> Durian aIter[7] -> EOF* aTree[] = { X， 5 0， 5 0， 3， 5， 6 } 根据前文所述的算法，由aTree[1]中存的是5，这说明当前的元素（最小的key值）是Ａｐｐｌｅ，它是迭代器５所指的ｋｅｙ的值。 当函数Next()被调用时，迭代器５将会前进到它的段中的下一个key值，假设下一个key是"Eggplant"，则有：aIter[5] -> Eggplant。 aTree[] = { X， 0 0， 6 0， 3， 5， 6 } 数组aTree[]的内容按如下方式更新：首先，比较迭代器５所指向的key的值和迭代器４的当前所指向的key值（迭代器4指向的key值仍然是"Grapefruit"）。这时，迭代器５所指向的key的值仍然是更小的，所以aTree[6]的值被设置为５。迭代器６所指向的key的值——"Durian"——比迭代器５所指向的key值（Eggplant）小，则aTree[3]被设置为6。而迭代器０所指的key的值（Banana）又比迭代器６所指的key的值小，即Banana<Durian，所以aTree[１]被设置成０。结果如下： aTree[] = { X， 0 0， 6 0， 3， 5， 6 } 也就是说，我们每次前进到ｓｏｒｔｅｒ的下一个元素，需要做log2(N)次的ｋｅｙ值比较，这里Ｎ是要被合并的段的数量。